package com.yequan.leetcode.sort;

/**
 * @author : Administrator
 * @date : 2020/6/27
 */
public class RecodeQuickSort {

    public static void main(String[] args) {
        int[] datas = new int[]{50, 10, 90, 30, 70, 40, 80, 60, 20};
        Recode5 quickSort = new Recode5();
        quickSort.quickSort(datas, 0, datas.length - 1);
        for (int data : datas) {
            System.out.println(data);
        }
    }

    static class Recode1 {
        public void quickSort(int[] data, int left, int right) {
            if (left < right) {
                int pivotIndex = partition(data, left, right);
                quickSort(data, left, pivotIndex - 1);
                quickSort(data, pivotIndex + 1, left);
            }
        }

        private int partition(int[] data, int left, int right) {
            int pivot = data[left];
            int i = left;
            int j = right;
            while (i != j) {
                while (data[j] > pivot && i < j) {
                    j--;
                }
                while (data[i] <= pivot && i < j) {
                    i++;
                }
                if (i < j) {
                    swap(data, i, j);
                }
            }
            data[left] = data[j];
            data[j] = pivot;
            return j;
        }

        private void swap(int[] data, int i, int j) {
            int temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }

    static class Recode2 {
        public void quickSort(int[] datas, int left, int right) {
            if (left < right) {
                int pivotIndex = partition(datas, left, right);
                quickSort(datas, left, pivotIndex - 1);
                quickSort(datas, pivotIndex + 1, right);
            }
        }

        private int partition(int[] datas, int left, int right) {
            int pivot = datas[left];
            int i = left;
            int j = right;
            while (i != j) {
                while (datas[j] > pivot && i < j) {
                    j--;
                }
                while (datas[i] <= pivot && i < j) {
                    i++;
                }
                if (i < j) {
                    swap(datas, i, j);
                }
            }
            datas[left] = datas[i];
            datas[j] = pivot;
            return j;
        }

        private void swap(int[] datas, int i, int j) {
            int temp = datas[i];
            datas[i] = datas[j];
            datas[j] = temp;
        }
    }

    static class Recode3 {
        public void quickSort(int[] datas, int left, int right) {
            if (left < right) {
                int pivotIndex = partition(datas, left, right);
                quickSort(datas, left, pivotIndex - 1);
                quickSort(datas, pivotIndex + 1, right);
            }
        }

        private int partition(int[] datas, int left, int right) {
            int pivot = datas[left];
            int i = left, j = right;
            while (i != j) {
                while (datas[j] > pivot && i < j) {
                    j--;
                }
                while (datas[i] <= pivot && i < j) {
                    i++;
                }
                if (i < j) {
                    swap(datas, i, j);
                }
            }
            datas[left] = datas[j];
            datas[j] = pivot;
            return j;
        }

        private void swap(int[] datas, int i, int j) {
            int temp = datas[i];
            datas[i] = datas[j];
            datas[j] = temp;
        }
    }

    static class Recode4 {
        public void quickSort(int[] datas, int left, int right) {
            if (left < right) {
                int pivotIndex = partition(datas, left, right);
                quickSort(datas, left, pivotIndex - 1);
                quickSort(datas, pivotIndex + 1, right);
            }
        }

        private int partition(int[] datas, int left, int right) {
            int pivot = datas[left];
            int i = left, j = right;
            while (i != j) {
                while (datas[j] > pivot && i < j) {
                    j--;
                }
                while (datas[i] <= pivot && i < j) {
                    i++;
                }
                if (i < j) {
                    swap(datas, i, j);
                }
            }
            datas[left] = datas[j];
            datas[j] = pivot;
            return j;
        }

        private void swap(int[] datas, int i, int j) {
            int temp = datas[i];
            datas[i] = datas[j];
            datas[j] = temp;
        }
    }

    static class Recode5 {
        public void quickSort(int[] datas, int left, int right) {
            //当子序列中只有一个元素时退出
            if (left >= right) {
                return;
            }
            int pivotIndex = partition(datas, left, right);
            //左子树快排
            quickSort(datas, left, pivotIndex - 1);
            //右子树快排
            quickSort(datas, pivotIndex + 1, right);
        }

        private int partition(int[] datas, int left, int right) {
            int pivot = datas[left];
            int i = left;
            int j = right;
            while (i != j) {
                //找出右边小于 pivot 的值的位置
                while (datas[j] > pivot && i < j) {
                    j--;
                }
                //找出左边大于 pivot 的值的位置
                while (datas[i] <= pivot && i < j) {
                    i++;
                }
                //交换位置
                if (i < j) {
                    swap(datas, i, j);
                }
            }
            //将 pivot 放入正确的位置
            datas[left] = datas[j];
            datas[j] = pivot;
            return j;
        }

        private void swap(int[] datas, int i, int j) {
            int temp = datas[i];
            datas[i] = datas[j];
            datas[j] = temp;
        }
    }

}
